package top.minuy.structure.graph.path.weighted;

import top.minuy.structure.graph.representations.table.WeightedGraph;

/**
 * BellmanFord 算法求解带权有向（无向）图有负权边的最短路径
 *
 * @author Minuy
 * @time 14:44
 * @date 2021/11/26
 */
public class BellmanFord {
    private WeightedGraph g; // 有权图
    private boolean hasNegativeCycle; // 是否含有负环
    private int[] dis; // 距离数组

    public BellmanFord(WeightedGraph g, int s) {
        this.g = g;

        g.validateVertex(s);

        dis = new int[g.V()];
        for (int i = 0; i < dis.length; i++) {
            dis[i] = Integer.MAX_VALUE;
        }

        dis[s] = 0;

        // 执行 V-1 次 BellmanFord 算法
        for (int pass = 1; pass < g.V(); pass++) {
            for (int v = 0; v < g.V(); v++) {
                for (int w : g.adj(v)) {
                    // 这里应该是v->w
                    // if (dis[w] != Integer.MAX_VALUE) {
                    if (dis[v] != Integer.MAX_VALUE) {
                        int newDis = dis[v] + g.getWeight(v, w);
                        if (newDis < dis[w]) {
                            // 这也不小心错了，应该是加上g.getWeight(v, w)后的值
                            // dis[w] = dis[v];
                            dis[w] = newDis;
                        }
                    }
                }
            }
        }

        // 第 V 次判断是否存在负权环
        for (int v = 0; v < g.V(); v++) {
            for (int w : g.adj(v)) {
                if (dis[v] != Integer.MAX_VALUE) {
                    int newDis = dis[v] + g.getWeight(v, w);
                    if (newDis < dis[w]) {
                        hasNegativeCycle = true;
                        return;
                    }
                }
            }
        }
    }

    /**
     * 查询顶点s是否与顶点t相连
     *
     * @param t 顶点t
     * @return boolean 是否相连
     * @author Minuy
     * @date 2021/11/26 14:56
     */
    public boolean isConnectedTo(int t) {
        g.validateVertex(t);
        return dis[t] != Integer.MAX_VALUE;
    }

    /**
     * 查询是否存在负权环
     *
     * @return boolean 是否存在负权环
     * @author Minuy
     * @date 2021/11/26 14:55
     */
    public boolean hasNegativeCycle() {
        return hasNegativeCycle;
    }

    /**
     * 获取源点s到目标顶点t的最短距离
     *
     * @param t 目标点t
     * @return int 源点s到目标顶点t的最短距离
     * @author Minuy
     * @date 2021/11/26 14:57
     */
    public int disTo(int t) {
        g.validateVertex(t);
        if (hasNegativeCycle) {
            throw new RuntimeException("Graph has Negative Cycle.");
        }
        return dis[t];
    }
}
